package _07剪邮票.拓展_连通性检测;

import java.util.Arrays;

/**
 路径压缩，在合并操作中，经过每条路径就加一条连线，
 把一路上遇到的对应的每个顶点的id数组值都设为到树根上，逼近了快速查找算法的理想状态。

 例四：压缩方法：使在通向树根的路中的每条连线都指向路劲中的下一个节点，
 即折半路径压缩的加权快速合并


 得到的与例三一样的净结果，比全路径压缩算法更简单。
 通过一系列的算法：找到了解决实际问题的好算法，它比较容易实现，
 且运行实际保证在收集数据项所花费时间的常数因子范围内。
 在这些算法中需要仔细和复杂的分析，才能找到最优算法。
 */
public class demo4 {

    public static void main(String[] args) {
        int N = 10;
        int id [] = new int[N];
        int sz [] = new int[N];
        for(int i = 0; i < N; i++){
            id[i] = i;
            sz[i] = 1;
        }
        int [] [] a =  new int [][]{
                {3,4},{4,9},{8,0},{2,3},{5,6},{2,9},
                {5,9},{7,3},{4,8},{5,6},{0,2},{6,1}
        };
        System.out.println(Arrays.toString(id));
        for(int [] s : a){
            int i, j, p = s[0], q = s[1];
            for(i = p; i != id[i]; i = id[i]){
                id[i] = id[id[i]];
            }
            for(j = q; j != id[j]; j = id[j]){
                id[j] = id[id[j]];
            }
            if(i == j){
                continue;
            }
            if(sz[i] < sz[j]){
                id[i] = j;
                sz[j] += sz[i];
            }else{
                id[j] = i;
                sz[i] += sz[j];
            }
            System.out.println(" " + p + " " + q);
            System.out.println(Arrays.toString(id));
            System.out.println(Arrays.toString(sz));
        }
    }
}